#include <iostream>
#include <stack>
#include <vector>
#include <cassert>
#include "BinaryTree.h"

using namespace std;

// struct TreeNode {
// 	int val;
// 	TreeNode *left;
// 	TreeNode *right;
// 	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

// 100.00 %
class Solution1
{
  public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		vector<int> v;
		preorder(root, v);
		return v;
	}
	void preorder(TreeNode *root, vector<int> &v)
	{
		if (!root)
			return;
		v.push_back(root->val);
		preorder(root->left, v);
		preorder(root->right, v);
	}
};

struct Command
{
	string s; // go, print
	TreeNode *node;
	Command(string s, TreeNode *node) : s(s), node(node) {}
};
// 100.00 %
class Solution
{
  public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		vector<int> res;
		if (root == NULL)
			return res;
		stack<Command> mystack;
		mystack.push(Command("go", root));
		while (!mystack.empty())
		{
			Command command = mystack.top();
			mystack.pop();
			if (command.s == "print")
			{
				res.push_back(command.node->val);
			}
			else
			{
				assert(command.s == "go");
				if (command.node->right)
					mystack.push(Command("go", command.node->right));
				if (command.node->left)
					mystack.push(Command("go", command.node->left));
				mystack.push(Command("print", command.node));
			}
		}
		return res;
	}
};

int main()
{
	int arr[] = {1, 0, 2, 3};
	int n = sizeof(arr) / sizeof(arr[0]);
	TreeNode *tree = createBinaryTree(arr, n);
	preorderPrint(tree);
	cout << endl;
	vector<int> vtree = Solution().preorderTraversal(tree);
	for (int i = 0; i < vtree.size() - 1; i++)
	{
		cout << vtree[i] << " ";
	}
	cout << vtree[vtree.size() - 1] << endl;
	deleteBinaryTree(tree);
	return 0;
}
